class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        int allSize = triangle.size();
        int d1Size = triangle.get(allSize - 1).size();
        int[][] dp = new int[allSize][d1Size];
        dp[0][0] = triangle.get(0).get(0);
        if (allSize==1){
            return  dp[0][0];
        }
        int shortPath = Integer.MAX_VALUE;
        for (int i = 1; i < allSize; i++) {
            int size = triangle.get(i).size();
            for (int j = 0; j < size; j++) {

                int min;
                if (j == 0) {
                    min = dp[i - 1][j];
                } else if (j == size - 1) {
                    min = dp[i - 1][j - 1];
                } else {
                    min = Math.min(dp[i - 1][j], dp[i - 1][j - 1]);
                }

                dp[i][j] = triangle.get(i).get(j) + min;

                if (i == allSize - 1) {
                    shortPath = shortPath > dp[i][j] ? dp[i][j] : shortPath;
                }
            }
        }
        return shortPath;
    }
}